package com.atguigu.prim;

import java.util.Arrays;

/**
 * @author RuiKnag
 * @create 2021-06-01-15:11
 */
/*
 * 最小生成树（MST）
 *   给定一个带权的无向连通图，如何选取生成一棵树，使得树上所有边的权的总和为最小，这就是最小生成树
 * N个顶点，最少n-1个边
 * 包含全部的顶点
 * n-1条边都在图中
 * 主要采用普利姆利算法和克鲁斯卡尔算法
 *
 * */
public class PrimAlgorithm {
    public static void main(String[] args) {
        //测试图的创建
        char[] data={'A','B','C','D','E','F','G'};
        int verxs=data.length;
        //邻接矩阵使用二维数组表示 100000表示这两个点无法联通
        int[][] weight={{10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000},
        };
        //创建MGraph对象
        MGraph mGraph = new MGraph(verxs);
        //创建minTree
        MinTree minTree = new MinTree();
        minTree.createGraph(mGraph,verxs,data,weight);
        minTree.show(mGraph);
        minTree.prim(mGraph,5);

    }

}
//创建最小生成树-->村庄图
class MinTree{
    //创建图的邻接矩阵
    public void createGraph (MGraph graph,int verxs,char[] data,int[][] weight){
        //图的顶点之间临界矩阵
        int i,j;
        for (i=0;i<verxs;i++){
            //图的顶点表示
            graph.data[i]=data[i];
            for(j=0;j<verxs;j++){
                graph.weight[i][j]=weight[i][j];
            }
        }
    }
    public void show(MGraph graph){
        for (int[] link: graph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }
    //编写prim算法生成最小树 图和开始的顶点
    public void prim(MGraph mGraph,int v){
        //定义一个标记数组
        int[] isVisited = new int[mGraph.verx];
        //将输入的节点进行标记
        isVisited[v]=1;
        //设置一个最小的边权重
        int minWeight=10000;
        //设置两个边
        int h1=-1;
        int h2=-1;
        //我们要输出的边数
        for(int k=1;k<mGraph.verx;k++){
            for (int i = 0; i < mGraph.verx; i++) {//表示我们被标记的顶点
                for (int j = 0; j < mGraph.verx; j++) {//表示我们未被标记的顶点
                    if (isVisited[i]==1&&isVisited[j]==0&&mGraph.weight[i][j]<minWeight){
                        h1=i;
                        h2=j;
                        minWeight=mGraph.weight[i][j];
                    }

                }
            }
            //输出当前最小的边
            System.out.println("<"+mGraph.data[h1]+" "+mGraph.data[h2]+">的权重值为"+mGraph.weight[h1][h2]);
            //对h2进行标记
            isVisited[h2]=1;
            //重置最小的边权重
            minWeight=10000;
        }

    }
}


class MGraph{
    int verx;//表示图的节点数
    char[] data;//存放节点数据
    int[][] weight;//存放边，这就是邻接矩阵

    public MGraph(int verx) {
        this.verx = verx;
        data=new char[verx];
        weight=new int[verx][verx];
    }
}
